package com.kevinkk.greedy;

import java.util.*;

/**
 * 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。
 * 每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
 * 请你重新构造并返回输入数组 people 所表示的队列
 */

/**
 * 这道题的排序规则有两个维度 h 和 k
 * 我们首先将数组按照身高 h 降序的方式进行排序
 * 然后再按照 k 进行插入操作
 */

public class QueueReconstructionByHeight {
    class Solution {
        public int[][] reconstructQueue(int[][] people) {
            List<int[]> list = new ArrayList<>();
            Arrays.sort(people,
                    // 身高相同，则按照 k 升序排序
                    (p1, p2) -> (p1[0] == p2[0]) ? (p1[1] - p2[1]) : (p2[0] - p1[0])
            );

            for (int i = 0; i < people.length; i++) {
                // add(index, element)
                list.add(people[i][1], people[i]);
            }

            return list.toArray(new int[people.length][]);
        }
    }
}
